/*
 * xpdiv.c
 *
 *  Created on: 06/07/2010
 *      Author: apollo
 */
/******************************************************************************
 * <Includes>
 *****************************************************************************/

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <xpdefines.h>
#include <xpdbg.h>
#include <xpdiv.h>
/******************************************************************************
 * <Defines>
 *****************************************************************************/

/******************************************************************************
 * <Typedefs>
 *****************************************************************************/
/******************************************************************************
 * <Local variables>
 *****************************************************************************/

/******************************************************************************
 * <Local declarations>
 *****************************************************************************/

/******************************************************************************
 * <Implementation>
 *****************************************************************************/

xpdiv* xpdiv_create()
{
    xpdiv *div = (xpdiv *)malloc(sizeof(xpdiv));
    memset((void *)div, 0, sizeof(xpdiv));

    return div;
}

xpdiv* xpdiv_createx(xpuint x, xpuint y, xpuint w, xpuint h)
{
    xpdiv *div = xpdiv_create();

    div->x = x;
    div->y = y;
    div->w = w;
    div->h = h;
    /*div root*/
    xpdiv_point *p = xpdiv_point_create();
    p->x = x;
    p->y = y;
    p->isAvail = TRUE;
    p->xnext = NULL;
    p->ynext = NULL;
    div->root = p;
    /*div topright*/
    p = xpdiv_point_create();
    if (w == (xpuint)-1)
        p->x = w;
    else
        p->x = x + w;
    p->y = y;
    p->isAvail = FALSE;
    p->xnext = NULL;
    p->ynext = NULL;
    div->root->xnext = p;
    /*bootomleft*/
    p = xpdiv_point_create();
    p->x = x;
    if (h == (xpuint)-1)
        p->y = h;
    else
        p->y = y + h;
    p->isAvail = FALSE;
    p->xnext = NULL;
    p->ynext = NULL;
    div->root->ynext = p;
    /*bottomleft*/
    p = xpdiv_point_create();
    if (w == (xpuint)-1)
        p->x = w;
    else
        p->x = x + w;
    if (h == (xpuint)-1)
        p->y = h;
    else
        p->y = y + h;
    p->isAvail = FALSE;
    p->xnext = NULL;
    p->ynext = NULL;

    div->root->xnext->ynext = p;
    div->root->ynext->xnext = p;

    return div;
}

void xpdiv_delete(xpdiv *div)
{
    xpdiv_point_delete(div->root);
    free((void *)div);
}

xpint xpdiv_rect_get(xpdiv *div, xpdiv_rect *rect)
{
    xpdiv_point *firstavail = NULL;
    xpuint maxwidth = 0;

    /*find first available*/
    xpdiv_point *yref = div->root;
    xpdiv_point *xref = NULL;
    while (yref != NULL)
    {
        xref = yref;
        while (xref != NULL)
        {
            if (xref->isAvail)
            {
                firstavail = xref;
                break;
            }
            xref = xref->xnext;
        }
        if (firstavail != NULL)
            break;
        yref = yref->ynext;
    }

    if (firstavail == NULL)
    {
        rect->x = (xpuint)-1;
        rect->y = (xpuint)-1;
        return -1;
    }

    rect->x = firstavail->x;
    rect->y = firstavail->y;
    /*first horizontal scan*/
    xref = firstavail->xnext;
    while (xref != NULL)
    {
        if (! xref->isAvail)
        {
            maxwidth = xref->x - firstavail->x;
            break;
        }
        xref = xref->xnext;
    }
    if (xref == NULL)
        maxwidth = (div->x + div->w) - firstavail->x;

    rect->w = maxwidth;
    rect->h = firstavail->ynext->y - firstavail->y;
    /*continue horizontal scan*/
    yref = firstavail->ynext;
    while (yref != NULL && yref->isAvail)
    {
        xpuint width = 0;
        xref = yref;
        while (xref != NULL && xref->isAvail)
        {
            width = xref->xnext->x - yref->x;
            xref = xref->xnext;
        }
        if (width < maxwidth)
            break;
        rect->h += (yref->ynext->y - yref->y);
        yref = yref->ynext;
    }
    return 0;
}

void xpdiv_point_insert(xpdiv *div, xpuint x, xpuint y)
{
    /*Insert column*/
    xpdiv_point *p = NULL;
    xpdiv_point *savedp = NULL;
    xpdiv_point *yref = NULL;
    xpdiv_point *xref = div->root;
    while (xref != NULL && xref->xnext != NULL && x > xref->x)
    {
        if (x < xref->xnext->x)
        {
            yref = xref;
            while (yref != NULL)
            {
                p = xpdiv_point_duplicate(yref);
                p->x = x;
                p->xnext = yref->xnext;
                p->ynext = NULL;
                yref->xnext = p;
                if (savedp != NULL)
                    savedp->ynext = p;
                savedp = p;
                yref = yref->ynext;
            }
            break;
        }
        xref = xref->xnext;
    }

    /*insert row*/
    savedp = NULL;
    yref = div->root;
    xref = NULL;
    while (yref != NULL && yref->ynext != NULL && y > yref->y)
    {
        if (y < yref->ynext->y)
        {
            xref = yref;
            while (xref != NULL)
            {
                p = xpdiv_point_duplicate(xref);
                p->y = y;
                p->ynext = xref->ynext;
                p->xnext = NULL;
                xref->ynext = p;
                if (savedp != NULL)
                    savedp->xnext = p;
                savedp = p;
                xref = xref->xnext;
            }
            break;
        }
        yref = yref->ynext;
    }
}

void xpdiv_rect_insert(xpdiv *div, xpdiv_rect *rect)
{
    xpdiv_point_insert(div, rect->x, rect->y);
    xpdiv_point_insert(div, rect->x, rect->y + rect->h);
    xpdiv_point_insert(div, rect->x + rect->w, rect->y + rect->h);
    xpdiv_point_insert(div, rect->x + rect->w, rect->y);
}

void xpdiv_rect_occupy(xpdiv *div, xpdiv_rect *rect)
{
    xpdiv_point *ref = div->root;

    /*x search*/
    while (ref != NULL && rect->x != ref->x)
        ref = ref->xnext;

    if (ref == NULL)
    {
        XPASSERT(FALSE)
        return;
    }

    /*y search*/
    while (ref != NULL && rect->y != ref->y)
        ref = ref->ynext;

    if (ref == NULL)
    {
        XPASSERT(FALSE);
        return;
    }

    if (ref->xnext == NULL
        || ref->ynext == NULL)
    {
        XPASSERT(FALSE);
        return;
    }

    xpuint ex = rect->x + rect->w;
    xpuint ey = rect->y + rect->h;
    xpdiv_point *yref = ref;
    xpdiv_point *xref;
    while (yref != NULL && ey > yref->y)
    {
        xref = yref;
        while (xref != NULL && ex > xref->x)
        {
            xref->isAvail = FALSE;
            xref = xref->xnext;
        }
        yref = yref->ynext;
    }
}

void xpdiv_rect_used(xpdiv *div, xpdiv_rect *rect)
{
    xpdiv_point *lastOccupied = NULL;

    xpdiv_point *xref = NULL;
    xpdiv_point *yref = div->root;
    while (yref != NULL && yref->ynext != NULL)
    {
        xref = yref;
        while (xref != NULL)
        {
            if (!xref->isAvail && xref->xnext != NULL)
                lastOccupied = xref;
            xref = xref->xnext;
        }
        yref = yref->ynext;
    }
    rect->x = div->x;
    rect->y = div->y;
    rect->w = div->w;
    if (lastOccupied != NULL)
        rect->h = lastOccupied->ynext->y;
    else
        rect->h = div->h;
}

void xpdiv_rect_newline(xpdiv *div, xpdiv_rect *rect)
{
    xpdiv_point *xref = NULL;
    xpdiv_point *yref = div->root;
    xpbool isDirty = FALSE;
    while (yref != NULL && yref->ynext != NULL)
    {
        xref = yref;
        isDirty = FALSE;
        while (xref != NULL)
        {
            if (!xref->isAvail)
                isDirty = TRUE;
            xref = xref->xnext;
        }
        if (!isDirty)
            break;
        yref = yref->ynext;
    }
    rect->x = yref->x;
    rect->y = yref->y;
    rect->w = div->w;
    if (div->h == (xpuint)-1)
        rect->h = div->h;
    else
        rect->h = yref->ynext->y - yref->y;
}

void xpdiv_rect_x(xpdiv *div, xpuint x, xpdiv_rect *rect)
{
    xpdiv_point *xref = NULL;
    xpdiv_point *yref = div->root;
    xpbool isSerched = FALSE;
    while (yref != NULL && yref->ynext != NULL)
    {
        xref = yref;
        while (xref != NULL)
        {
            if (xref->isAvail && xref->x == x)
            {
                isSerched = TRUE;
                break;
            }
            xref = xref->xnext;
        }
        if (isSerched)
            break;
        yref = yref->ynext;
    }
    rect->x = xref->x;
    rect->y = xref->y;
    yref = xref;

    while (xref != NULL && xref->xnext != NULL)
    {
        if (xref->isAvail)
            rect->w = xref->xnext->x - rect->x;
        else
            break;
        xref = xref->xnext;
    }
    yref = yref->ynext;
    xpuint w = 0;
    while (yref != NULL && yref->ynext != NULL)
    {
        xref = yref;
        while (xref != NULL && xref->xnext != NULL)
        {
            if (xref->isAvail)
                w = xref->xnext->x - rect->x;
            else
                break;
            if (w >= rect->w)
                break;
            xref = xref->xnext;
        }
        if (w < rect->w)
            break;
        rect->h = yref->ynext->y - rect->y;
    }
    if (yref->ynext == NULL && yref->y == (xpuint)-1)
        rect->h = yref->y;
}

xpdiv_point* xpdiv_point_create()
{
    xpdiv_point *p = (xpdiv_point *)malloc(sizeof(xpdiv_point));
    memset((void *)p, 0, sizeof(xpdiv_point));

    return p;
}

void xpdiv_point_delete(xpdiv_point *point)
{
    if (point == NULL)
        return;
    xpdiv_point_delete(point->xnext);
    xpdiv_point_delete(point->ynext);
}

xpdiv_point* xpdiv_point_duplicate(xpdiv_point *point)
{
    if (point == NULL)
        return NULL;
    xpdiv_point *p = (xpdiv_point *)malloc(sizeof(xpdiv_point));
    memcpy((void *)p, (void *)point, sizeof(xpdiv_point));
    return p;
}

